package medium.差分数组;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 创建时间：2025-05-22 10:25
 */
public class 零数组变换III_3362 {
    public int maxRemoval(int[] nums, int[][] queries) {
        Arrays.sort(queries, Comparator.comparingInt(a -> a[0]));
        // 构建最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        int n = nums.length;
        int[] diff = new int[n+1];
        int s = 0; //表示前i个diff的和
        for (int i = 0, j = 0; i < n; i++) {
            s += diff[i];
            // 找出queries中所有左端点在i之前的操作的右端点（因为从0开始，所以我觉得==i也可以）
            while(j < queries.length && queries[j][0] <= i ) {
                maxHeap.add(queries[j][1]);
                j++;
            }
            // 查找右端点中>=i的且s小于nums[i]
            while(!maxHeap.isEmpty() && maxHeap.peek() >= i && s <nums[i]) {
                diff[maxHeap.poll()+1]--;
                s++;
            }
            if (s < nums[i]) {
                return -1;
            }
        }
        return maxHeap.size();
    }
}
